package heap_1101;

import java.util.Arrays;

public class HeapOperations {
    // 假设是小堆
    // 满足可以向下调整的前提
    // int 类型做下标用
    // long 类型做元素使用
    public static void adjustDown递归(long[] array, int size, int index) {
        // 1) 检查要调整的位置 [index] 是不是一个叶子结点
        // 如果是叶子结点，直接结束调整即可
        int leftIdx = 2 * index + 1;
        if (leftIdx >= size) {
            // 没有左孩子 -> 叶子结点
            return;
        }

        // 2) 找到最小的一个孩子
        // 不是叶子 -> 肯定有左孩子
        // 请问一定有右孩子么？
        // 没有右孩子：最小的是左孩子
        // 如果右孩子 && 左孩子的值 < 右孩子的值：最小的是左孩子
        // 如果右孩子 && 左孩子的值 == 右孩子的值：最小的是左孩子 或者 右孩子
        // 如果右孩子 && 左孩子的值 >右孩子的值：最小的是右孩子
        int minIdx = leftIdx;       // 先假设最小的孩子是左孩子
        // 只有右孩子存在 && 右 < 左，才改成右
        int rightIdx = leftIdx + 1; // 2 * index + 2;
//        if (rightIdx < size && array[rightIdx] < array[leftIdx]) {
//            // 这里因为有短路的特性，才能这么写
//            // 先判断 rightIdx < size 保证有右孩子（右孩子的下标合法）
//            // 然后才能比较两个孩子的值（根据右孩子下标取数组的值）
//            minIdx = rightIdx;
//        }

        // 假设没有 && 的短路特性，就得这么写
        if (rightIdx < size) {
            if (array[rightIdx] < array[leftIdx]) {
                minIdx = rightIdx;
            }
        }

        // 3) 比较 "我" 和最小孩子的值
        if (array[index] <= array[minIdx]) {
            // "我" 这个位置也满足堆的性质
            return;
        }

        // 4) "我" 这个位置不满足堆的性质
        swap(array, index, minIdx);

        // 5) 交换完了不算完，因为新的位置需要在做判断
        // 刚刚交换的最小孩子的位置可能出问题了
        adjustDown递归(array, size, minIdx);
    }

    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    // 更常用的非递归的向下调整
    public static void adjustDown小堆(long[] array, int size, int index) {
        while (2 * index + 1 < size) {  // 说明不是叶子
            // 找到最小的孩子
            int minIdx = 2 * index + 1;
            if (minIdx + 1 < size && array[minIdx + 1] < array[minIdx]) {
                minIdx++;
            }

            // 判断 "我" 和最小孩子的关系
            if (array[index] <= array[minIdx]) {
                return;
            }

            // 交换
            swap(array, index, minIdx);
            // 以最小孩子的位置再次这个过程
            index = minIdx;
        }
    }

    public static void adjustDown大堆(long[] array, int size, int index) {
        while (2 * index + 1 < size) {  // 说明不是叶子
            // 找到最大的孩子
            int maxIdx = 2 * index + 1;
            if (maxIdx + 1 < size && array[maxIdx + 1] > array[maxIdx]) {
                maxIdx++;
            }

            // 判断 "我" 和最大孩子的关系
            if (array[index] >= array[maxIdx]) {
                return;
            }

            // 交换
            swap(array, index, maxIdx);
            // 以最大孩子的位置再次这个过程
            index = maxIdx;
        }
    }

    public static void createHeap大堆(long[] array, int size) {
        // 直接求最后一个元素的双亲的下标
        // ci = (size - 1)
        // pi = (ci - 1) / 2
        int pIdx = (size - 2) / 2;

        // O(n * log(n))
        // O(n)
        for (int i = pIdx; i >= 0; i--) {    // n 次
            adjustDown大堆(array, size, i);   // O(log(n))
        }
    }


    public static void main(String[] args) {
//        // 传入的数组需要满足可以向下调整的前提
//        long[] array = { 10, 3, 13, 2, 2, 7, 8, 0, 0, 0, 0 };
//        int size = 7;
//        // 要调整的位置是 [0]
//        adjustDown大堆(array, size, 0);

//        long[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
//        int size = array.length;
//        adjustDown小堆(array, size, 0);
//        System.out.println(
//                Arrays.toString(    // 数组变成我们需要的字符串
//                        Arrays.copyOf(array, size)  // 复制前 size 个元素作为新数组
//                )
//        );

        long[] array = { 9, 3, 1, 7, 6, 9, 2, 8, 4, 0, 0, 3, 6, -1, -1, -1 };
        int size = 13;
        createHeap大堆(array, size);
        System.out.println(
                Arrays.toString(    // 数组变成我们需要的字符串
                        Arrays.copyOf(array, size)  // 复制前 size 个元素作为新数组
                )
        );

    }
}
